#include <bits/stdc++.h>

using namespace std;

// N皇后问题
// 测试链接 : https://leetcode.cn/problems/n-queens-ii/

class Solution 
{
public:
    // 用数组表示路径实现的N皇后问题，不推荐
    int totalNQueens1(int n) 
    {
        if(n < 1) return 0;
        vector<int> path(n);
        return f1(0, path, n);
    }

	// i : 当前来到的行
	// path : 0...i-1行的皇后，都摆在了哪些列
	// n : 是几皇后问题
	// 返回 : 0...i-1行已经摆完了，i....n-1行可以去尝试的情况下还能找到几种有效的方法
    int f1(int i, vector<int>& path, int n)
    {
        if(i == n) return 1;

        int ans = 0;
        for(int j = 0; j < n; ++j)
        {
            if(check(path, i, j))
            {
                path[i] = j;
                ans += f1(i + 1, path, n);
            }
        }
        return ans;
    }

	// 当前在i行、j列的位置，摆了一个皇后
	// 0...i-1行的皇后状况，path[0...i-1]
	// 返回会不会冲突，不会冲突，有效！true
	// 会冲突，无效，返回false
    bool check(vector<int>& path, int i, int j)
    {
        // 当前 i
		// 当列 j
        for(int k = 0; k < i; ++k)
        {
            // 0...i-1
			// 之前行 : k
			// 之前列 : path[k]
            if(j == path[k] || abs(i - k) == abs(j - path[k])) return false;
        }
        return true;
    }

	// 用位信息表示路径实现的N皇后问题，推荐
    int totalNQueens2(int n) 
    {
        if(n < 1) return 0;
		// n = 5
		// 1 << 5 = 0...100000 - 1
		// limit  = 0...011111; 
		// n = 7
		// limit  = 0...01111111; 
        int limit = (1 << n) - 1;
        return f2(limit, 0, 0, 0);
    }

	// limit : 当前是几皇后问题
	// 之前皇后的列影响：col
	// 之前皇后的右上 -> 左下对角线影响：left
	// 之前皇后的左上 -> 右下对角线影响：right
    int f2(int limit, int col, int left, int right)
    {
        // 所有皇后放完了！
        if(col == limit) return 1;
        // 总限制
        int ban = col | left | right;
        // ~ban : 1可放皇后，0不能放
        int candidate = limit & (~ban);
        // 放置皇后的尝试！
        int place = 0;
        // 一共有多少有效的方法
        int ans = 0;
        while(candidate != 0)
        {
            // 提取出最右侧的1（lowbit）
            place = candidate & (-candidate);
            candidate ^= place;
            ans += f2(limit, col | place, (left | place) >> 1, (right | place) << 1);
        }
        return ans;
    }
};

// 另一种写法
class Solution 
{
private:
    int n, ret;
    bool checkCol[10], checkDig1[20], checkDig2[20];

    void dfs(int row)
    {
        if(row == n)
        {
            ++ret;
            return;
        }

        for(int col = 0; col < n; ++col)
        {
            if(!checkCol[col] && !checkDig1[row - col + n] && !checkDig2[row + col])
            {
                checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = true;
                dfs(row + 1);
                checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = false;
            }
        }
    }

public:
    int totalNQueens(int N) 
    {
        n = N;
        dfs(0);
        return ret;
    }
};